1. Field of the Invention
This invention generally relates to processing Low Density Parity check codes, and more specifically, to processing these codes using a deterministic data cache.
2. Background Art
Low Density Parity Check (LDCP) codes are used to compress, or encode, data. These codes are used in a number of technologies including mobile communications and video compression. In video compression, for example, LDPC codes are used in a Wyner-Ziv coding process. This process provides simple, low cost encoding with low computational complexity by shifting the computational load from the encoder to the decoder.
Briefly speaking, in Wyner-Ziv coding, the decoder has access to side information that is not available to the encoder, and such side information can still be exploited to achieve greater compression than would otherwise be possible. Therefore, with the objective to achieve very low encoding complexity, Wyner-Ziv video coding systems exploit the statistical correlation among neighboring video frames only at the decoder, and thus relieve the encoder of significant computational load.
In general, a Wyner-Ziv video compression system is comprised of a video encoder, which compresses (or encodes) a video signal into a compressed video frame, and a video decoder, which decompresses (or decodes) the compressed video frame to produce a reconstructed video frame. At any time instant, a video frame V is to be encoded by the encoder Since the decoder has access to the previously decoded frame Vo, it can generate prior knowledge about V from the previously decoded frame Vo, and use this knowledge in the decoding process. Being aware of the existence of the prior knowledge about Vo at the decoder, the encoder can transmit fewer bits, and thus achieve greater compression, than would otherwise be possible.
The real time processing of the decoding algorithm, referred to as the Belief Propagation algorithm, for an LDPC decoder in a Wyner-Ziv based video decoder involves processing of up to 50 iterations per frame where each frame contains of tens to hundreds of thousand of LDPC probability vectors, each of which may be 16 to 32 elements of 2 to 4 bytes per element, at a rate of 30 frames per second. In order to be able to process this amount of information a hardware accelerator is currently required. One of the main obstacles in processing such large numbers of LDPC codes is the prohibitively huge memory bandwidth requirements. This problem is compounded by the fact that memory accesses are random, non-sequential, and consequently bursting memories such as DRAM are of little benefit. Even increasing the size of memory data widths has a limited effect because there is no advantage to making buses larger than the width of a single LDPC code. Consequently the best way to increase the necessary bandwidth is to use multi-ported high-speed memories. Multi-ported memories tend to be prohibitively expensive if implemented as standalone external memories and are consequently more efficient if implemented as memory objects internal to a chip. Internal memories also have the advantage of being able to be clocked at a higher rate than external memories. However, internal memories tend to be limited in size compared to external memories and therefore limit the overall number of LDPC codes that can be processed.
In order to get the optimum performance and allow for large number of LDPC codes, it is desirable to adapt standard processing techniques such as caching which allows for a more efficient memory subsystem implementation. However, the caching requirements for processing LDPC codes differs significantly from the requirements of standard CPU based systems. Standard processor caches are designed to rely on processing programs, which statistically operate within a limited region long enough for the caches to be of significant use. LDPC codes tend to be more efficient as they span large regions that are consequently not readily localized. This makes the standard statistically based caches inefficient for processing LDPC codes. There are other advantages to processing LDPC codes and these are: (1) the code maps are deterministic and do not have to be processed dynamically but can be characterized once and from there on used repeatedly; and (2) the order of the processing can be reordered to best take advantage of any localization to optimize cache utilization.